﻿using System;
using System.Globalization;
using System.Security.Cryptography;

namespace h3
{
    // public class Solution
    // {
    //     public int CountPrimes(int n)
    //     {
    //         if (CheckOneOrTwo(n))
    //         {
    //             return 0;
    //         }
    //         else//more than 2
    //         {
    //             int times = 0;
    //             for (int temp = 2; temp < n; temp++)
    //             {
    //                 if (IsPrime(temp))
    //                 {
    //                     times += 1;
    //                     // Console.WriteLine(temp);
    //                 }
    //             }
    //
    //
    //             return times;
    //         }
    //
    //         return 0;
    //     }
    //
    //     public bool CheckOneOrTwo(int n)
    //     {
    //         if (n == 0 || n == 1 || n == 2)
    //         {
    //             return true;
    //         }
    //         else
    //         {
    //             return false;
    //         }
    //     }
    //
    //     public bool IsPrime(int num)
    //     {
    //         int half = num / 2;
    //         if (num == 2)
    //         {
    //             return true;
    //         }
    //         for (int temp = 2; temp <= half; temp++)
    //         {
    //             if (num % temp == 0)
    //             {
    //                 return false;
    //             }
    //         }
    //         return true;
    //     }
    //
    // }

    public class Solution
    {
        public int CountPrimes(int n)
        {
          bool [] a=new bool[n+1];
          int count = 0;
          for(int i = 2; i < n; i++)
              a[i] = true;
    
          for(int i = 2; i < n; i++)
              if(a[i])
              {
                  count++;
                  for(int j = 2 * i; j < n; j += i)
                      a[j] = false;
              }
    
          return count;
        }
    }
}